# 131.分割回文串
# 给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串 。返回s所有可能的分割方案。
# 回文串是正着读和反着读都一样的字符串。
#
# 示例1：
# 输入：s = "aab"
# 输出：[["a", "a", "b"], ["aa", "b"]]
#
# 示例2：
# 输入：s = "a"
# 输出：[["a"]]



class Solution:
    def ishuiwen(self,s):
        left, right = 0, len(s)-1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return False
        return True
    def partition(self, s: str):
        res = []
        path = []
        size = len(s)
        def backtracking(s,index):
            # 切割到字符串末尾，就结束了
            if index >= len(s):
                res.append(path[:])
                return
            # 单层递归逻辑
            for i in range(index,len(s)):
                # 此次比其他组合多一层判断
                if self.ishuiwen(s[index:i+1]):
                    path.append(s[index:i+1])
                    backtracking(s,i+1)
                    path.pop()
                else:continue
        backtracking(s,0)
        return res

class A:
    def __init__(self):
        self.paths = []
        self.path = []

    def partition(self, s: str):
        '''
        递归用于纵向遍历
        for循环用于横向遍历
        当切割线迭代至字符串末尾，说明找到一种方法
        类似组合问题，为了不重复切割同一位置，需要start_index来做标记下一轮递归的起始位置(切割线)
        '''
        self.path.clear()
        self.paths.clear()
        self.backtracking(s, 0)
        return self.paths

    def backtracking(self, s: str, start_index: int) -> None:
        # Base Case
        if start_index >= len(s):
            self.paths.append(self.path[:])
            return

        # 单层递归逻辑
        for i in range(start_index, len(s)):
            # 此次比其他组合题目多了一步判断：
            # 判断被截取的这一段子串([start_index, i])是否为回文串
            if self.is_palindrome(s, start_index, i):
                self.path.append(s[start_index:i + 1])
                self.backtracking(s, i + 1)  # 递归纵向遍历：从下一处进行切割，判断其余是否仍为回文串
                self.path.pop()  # 回溯
            else:
                continue

    def is_palindrome(self, s: str, start: int, end: int) -> bool:
        i: int = start
        j: int = end
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

if __name__ == '__main__':
    s = "aaba"
    tmp = Solution()
    res = tmp.partition(s)
    print(res)

